# Nikhil Ketkar, Wed Feb 13 15:43:26 PST 2008

def float2rational(a):
    if len(repr(a).split('e')) == 2:
        coefficient = repr(a).split('e')[0] 
        exponent = int(repr(a).split('e')[1])
    elif len(repr(a).split('e')) == 1:
        coefficient = repr(a).split('e')[0] 
        exponent = 1

    if len(coefficient.split('.')) == 2:
        point_up = len(coefficient.split('.')[0])
        point_down = len(coefficient.split('.')[1])
    elif len(coefficient.split('.')) == 1:
        point_up = len(coefficient.split('.')[0])
        point_down = 0

    numerator = int(coefficient.replace('.',''))
    denominator = 10 ** point_down 
    
    if exponent > 1:
        numerator = numerator * exponent
    elif exponent < 0:
        denominator = denominator * (10 ** abs(exponent))
        
    return (numerator, denominator)

def positiveRational():
    def sds(n):
        if n == 0: return 0
        elif n == 1: return 1
        elif n % 2 == 0: return sds(n/2)
        elif n % 2 == 1: return sds(n/2) + sds(n/2 + 1)
    n = 0
    while True:
        yield Rational(sds(n),sds(n+1))
        n += 1
    
class Rational(object):
    def __init__(self,num, den = None):
        if isinstance(num,int) and (den is None) or\
                isinstance(num,long) and (den is None):
            self.num = num
            self.den = 1
        elif isinstance(num,float) and (den is None):
            self.num, self.den = float2rational(num)
        elif isinstance(num,Rational) and (den is None):
            self.num = num.num
            self.den = num.den
        elif isinstance(num, Rational) and isinstance(den, Rational):
            self.num = num.num * den.den
            self.den = num.den * den.num
        elif (isinstance(num,int) and isinstance(den,int)) or \
                (isinstance(num,long) and isinstance(den,long)) or \
                (isinstance(num,int) and isinstance(den,long)) or \
                (isinstance(num,long) and isinstance(den,int)):
            self.num = num
            self.den = den
        self.reduce()
    def reduce(self):
        def gdc(a,b):
            if b == 0: return a
            else: return gdc(b, a % b)
        gdc_value = gdc(self.num,self.den)
        self.num /= gdc_value 
        self.den /= gdc_value
    def __add__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.den + rational_operand.num * self.den
        den = self.den * rational_operand.den
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational
    def __radd__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.den + rational_operand.num * self.den
        den = self.den * rational_operand.den
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational
    def __sub__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.den - rational_operand.num * self.den
        den = self.den * rational_operand.den
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational
    def __mul__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.num
        den = self.den * rational_operand.den
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational        
    def __rmul__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.num
        den = self.den * rational_operand.den
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational        
    def __div__(self, operand):
        rational_operand = Rational(operand)
        num =  self.num * rational_operand.den
        den = self.den * rational_operand.num
        return_rational = Rational(num,den)
        return_rational.reduce()
        return return_rational
    def __pow__(self,operand):
        num = self.num
        den = self.den
        if operand == 0:
            return Rational(0,0)
        elif operand > 0:
            final_num = num
            final_den = den
            for i in xrange(1,operand):
                final_num *= num
                final_den *= den
            return Rational(final_num,final_den)       
        elif operand < 0:
            final_num = num
            final_den = den
            for i in xrange(1,operand):
                final_num *= num
                final_den *= den
            return Rational(final_den,final_num)       
    def __cmp__(self, operand):
        rational_operand = Rational(operand)
        if self.num == rational_operand.num and self.den == rational_operand.den:
            return 0
        else:
            if self.num * rational_operand.den > rational_operand.num * self.den:
                return 1
            else:
                return -1            
    def __str__(self):
        return "(" + str(self.num).strip('L') + "/" + str(self.den).strip('L') + ")"

if __name__ == "__main__":
    from math import *
    
    r0 = Rational(3,2)
    r1 = Rational(5,17)
    print "r0:", r0
    print "r1:", r1
    print "r0 + r1:", r1 + r0 
    print "r0 - r1:", r0 - r1
    print "r0 * r1:", r0 * r1
    print "r0 / r1:", r0 / r1
    print "r0 ** 20:", r0 ** 20
    print "r0 + 1:", r0 + 1
    print "r1 * 3:", r1 * 3
    print "r0 < r1:", r0 < r1
    print "r0 > r1:", r0 > r1
    print "Rational(pi):", Rational(pi)
    print "Rational(2**0.5):", Rational(2**0.5)
    rati = positiveRational()
    print "Using Iterator tp print the first 10 rational numbers: " 
    for i in xrange(1,10):
        print rati.next()



